/**
 * Copyright 2012
 * VAN
 */
package vaidyaa.algorithms.sorting;

/**
 * @author vaidyaa
 * 
 */
public class MergeSortService implements SortService {

	@Override
	public void sort(Integer[] array, boolean order) {
		int start = 0;
		int end = array.length - 1;
		mergeSort(array, start, end, order);
	}

	private void mergeSort(Integer array[], int start, int end, boolean order) {
		if (start == end) {
			return;
		}
		int middle = (start + end) / 2;
		mergeSort(array, start, middle, order);
		mergeSort(array, middle + 1, end, order);
		mergePartitionsInOrder(array, start, middle, end, order);
	}

	private void mergePartitionsInOrder(Integer[] array, int start, int middle,
			int end, boolean order) {
		Integer[] leftArray = new Integer[middle - start + 1];
		Integer[] rightArray = new Integer[end - middle];
		Integer[] mergedArray = new Integer[end -start + 1];
		for (int i = start; i < middle + 1; i++) {
			leftArray[i - start] = array[i];
		}
		for (int i = middle + 1; i < end + 1; i++) {
			rightArray[i - middle - 1] = array[i];
		}
		int i = 0;
		int j = 0;
		for (; (start + i + j) < end + 1;) {
			int left = (i < leftArray.length) ? leftArray[i] : leftArray[leftArray.length - 1];
			int right = (j < rightArray.length) ? rightArray[j] : rightArray[rightArray.length - 1];
			if ((!SortingCommons.compare(left, right, order) || j >= rightArray.length) && i < leftArray.length) {
				mergedArray[i + j] = left;
				i++;
			} else {
				mergedArray[i + j] = right;
				j++;
			}
		}
		for (i = 0; (start + i) < end + 1; i++) {
			array[start + i] = mergedArray[i];
		}
		
	}
}
